Image output devices for imaging systems, such as display monitors and printers, operate as raster devices. In these types of devices, the output image comprises a two-dimensional grid of picture elements, or pixels, which is known as a "raster". To generate an image on a screen or a page, these devices store a representation in memory of a display value for each pixel in the image. This stored representation of the image is referred to as a "pixel map" (sometimes abbreviated "pixmap"), or a frame buffer. The display value for each pixel comprises multiple components, e.g. red, green and blue components for a monitor which operates in an RGB color space, or cyan, magenta and yellow components for a printer which operates in a CMY color space.
In the operation of an exemplary imaging system, a user might be running a graphics application program on a computer. The user can instruct the program to draw an object, such as a square, at a particular location on the screen of the display monitor. The user might also designate that the square be filled with a certain color, such as 50% purple. In response to these user inputs, the graphics program issues high-level instructions to the computer's operating system to draw a 50% purple square. A display manager, or similar such portion of the computer's operating system for controlling the operation of the display monitor, interprets the command to draw a 50% purple square into low-level instructions for the display monitor. As part of this interpretation process, the high-level description of the purple square from the application program is translated into individual red, green and blue pixel display values that are stored in the frame buffer. In this particular example, each entry in the frame buffer for a corresponding display pixel that is covered by the square stores value of 50% red, 50% blue and 0% green. If the output device is a printer, corresponding values for cyan, magenta and yellow are stored in the frame buffer.
The process of converting the high-level graphical data into pixel values is known as rendering. In a device which employs a three-dimensional color space, such as RGB or CMY, the frame buffer is comprised of three sections, or planes, which respectively relate to the three components. For each pixel of an image, the rendering process involves the steps of determining the display value for one of the components, e.g. the red component, storing that value at an appropriate location in the corresponding section of the frame buffer, and repeating these steps for each of the other two components. In other words, each of the three color space components is individually rendered for each pixel.
The rendering process requires an appreciable amount of processing power, and hence time, in the overall generation of an image. As a general objective, therefore, it is desirable to optimize the rendering process wherever possible, and thereby improve the efficiency with which images are generated. One area of particular interest in this regard pertains to overlapping graphical objects. Typically, each individual object in an image is separately rendered. For example, if the user creates an image containing three overlapping rectangles, when this image is to be displayed on a monitor or printed on a printer, the first rectangle to have been created by the user is initially rendered, followed by the second rectangle and then the third rectangle. In the areas where the rectangles overlap, the information pertaining to the later-generated rectangle overwrites the pixel data for the earlier-generated rectangle, to account for the opacity of the objects. This procedure, by which later-generated data replaces earlier-generated data, is known as the "painter's algorithm." In essence, data for a later object is "painted over" the data for an earlier object in the frame buffer.
It can be seen that the rendering process is inherently inefficient when overlapping objects are present in the image. Since each object is individually rendered, earlier-generated objects are rendered without consideration of later-generated objects. As a result, any rendering that is carried out with respect to a portion of an object that is obscured by a later-generated object is unnecessary, inefficient and results in wasted processing time. It is desirable, therefore, to avoid rendering portions of objects which are obscured by other objects in an image.